Abstract: In this paper a watermark embedding and recovery technique is proposed based on the compressed sensing theorem. Both host image and watermark are sparse, each in frequency domain using DWT. In recovery, new method called Least Support Matching Pursuit (LS-OMP) is used to recover the watermark and the host image in clean conditions.LS-OMP algorithm adaptively chooses optimum L (Least Part of support), at each iteration. This new algorithm has some important characteristics: it has a low computational complexity comparing with ordinary OMP method, the reconstruction accuracy is show better results than the other method. Second, we give the procedure for the invisible image watermarking in the presence of compressive sampling. The image reconstruction based on a set of watermarked measurements is performed using LS-OMP. While the LS-OMP offers a comparably theoretical guarantee as best optimization–based approach, simulation results show that it outperforms many algorithms especially for compressible signals.

Keywords: Compressed sensing, lest Support Orthogonal Matching Pursuit, Orthogonal matching pursuit, restricted isometry property, Watermark.